package com.xzz.dp;

import java.util.Arrays;

/**
 * @author: hhz
 * @create: 2022-01-12 09:08
 * 334. 递增的三元子序列
 * 给你一个整数数组nums ，判断这个数组中是否存在长度为 3 的递增子序列。
 *
 * 如果存在这样的三元组下标 (i, j, k)且满足 i < j < k ，使得nums[i] < nums[j] < nums[k] ，返回 true ；否则，返回 false 。
 *
 **/
public class IncreasingTriplet {
    public static void main(String[] args) {
        System.out.println(increasingTriplet(new int[]{1,2,3,4,5}));
        System.out.println(increasingTriplet(new int[]{5,4,3,2,1}));
        System.out.println(increasingTriplet(new int[]{2,1,5,0,4,6}));
        System.out.println();
        System.out.println(increasingTriplet2(new int[]{1,2,3,4,5}));
        System.out.println(increasingTriplet2(new int[]{5,4,3,2,1}));
        System.out.println(increasingTriplet2(new int[]{2,1,5,0,4,6}));
    }
    public static boolean increasingTriplet(int[] nums) {
        if(nums.length<3){
            return false;
        }
        //贪心
        int a = Integer.MAX_VALUE;
        int b = Integer.MAX_VALUE;
        for (int num : nums) {
           if(num<=a){
               a = num;
           }else if(num<=b){
               b = num;
           }else {
               return true;
           }
        }
        return false;
    }
    //二分
    public static boolean increasingTriplet2(int[] nums) {
        if(nums.length<3){
            return false;
        }
        int[] top = new int[nums.length];
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            int left = 0;
            int right = res;
            while (left<right){
                int mid = left+(right-left)/2;
                if(top[mid]<nums[i]){
                    left = mid+1;
                }else if(top[mid]>nums[i]){
                    right = mid;
                }else {
                    right = mid;
                }
            }
            if(left==res){
                res++;
                if(res>2){
                    return true;
                }
            }
            top[left] = nums[i];
        }
        return false;
    }
}
